Remove invalid parentheses

Time: O(C(N,C)); Space: O(C); hard

Remove the minimum number of invalid parentheses in order to make the input string valid.

Return all possible results.

Note:

  • The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: s = “()())()”

Output: [“()()()”, “(())()”]

Example 2:

Input: s = “(a)())()”

Output: [“(a)()()”, “(a())()”]

Example 3:

Input: s = “)(”

Output: [“”]

Hints:

  1. Since we don’t know which of the brackets can possibly be removed, we try out all the options!

  2. We can use recursion to try out all possibilities for the given expression. For each of the brackets, we have 2 options: We keep the bracket and add it to the expression that we are building on the fly during recursion. OR, we can discard the bracket and move on.

  3. The one thing all these valid expressions have in common is that they will all be of the same length i.e. as compared to the original expression, all of these expressions will have the same number of characters removed. Can we somehow find the number of misplaced parentheses and use it in our solution?

  4. The one thing all these valid expressions have in common is that they will all be of the same length i.e. as compared to the original expression, all of these expressions will have the same number of characters removed. Can we somehow find the number of misplaced parentheses and use it in our solution?

  5. For every left parenthesis, we should have a corresponding right parenthesis. We can make use of two counters which keep track of misplaced left and right parenthesis and in one iteration we can find out these two values.

    • 0 1 2 3 4 5 6 7

    • ( ) ) ) ( ( ( )

    • i = 0, left = 1, right = 0

    • i = 1, left = 0, right = 0

    • i = 2, left = 0, right = 1

    • i = 3, left = 0, right = 2

    • i = 4, left = 1, right = 2

    • i = 5, left = 2, right = 2

    • i = 6, left = 3, right = 2

    • i = 7, left = 2, right = 2

    • We have 2 misplaced left and 2 misplaced right parentheses.

  6. We found out that the exact number of left and right parenthesis that has to be removed to get a valid expression. So, e.g. in a 1000 parentheses string, if there are 2 misplaced left and 2 misplaced right parentheses, after we are done discarding 2 left and 2 right parentheses, we will have only one option per remaining character in the expression i.e. to consider them. We can’t discard them.

[1]:

class Solution1(object):
    """
    Time:  O(C(N,C)), try out all possible substrings with the minimum C deletion.
    Space: O(C), the depth is at most C, and it costs N at each depth
    """
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        # Calculate the minimum left and right parantheses to remove
        def findMinRemove(s):
            left_removed, right_removed = 0, 0
            for c in s:
                if c == '(':
                    left_removed += 1
                elif c == ')':
                    if not left_removed:
                        right_removed += 1
                    else:
                        left_removed -= 1
            return (left_removed, right_removed)

        # Check whether s is valid or not.
        def isValid(s):
            sum = 0
            for c in s:
                if c == '(':
                    sum += 1
                elif c == ')':
                    sum -= 1
                if sum < 0:
                    return False
            return sum == 0

        def removeInvalidParenthesesHelper(start, left_removed, right_removed):
            if left_removed == 0 and right_removed == 0:
                tmp = ''
                for i, c in enumerate(s):
                    if i not in removed:
                        tmp += c
                if isValid(tmp):
                    res.append(tmp)
                return

            for i in range(start, len(s)):
                if right_removed == 0 and left_removed > 0 and s[i] == '(':
                    if i == start or s[i] != s[i - 1]:  # Skip duplicated.
                        removed[i] = True
                        removeInvalidParenthesesHelper(i + 1, left_removed - 1, right_removed)
                        del removed[i]
                elif right_removed > 0 and s[i] == ')':
                    if i == start or s[i] != s[i - 1]:  # Skip duplicated.
                        removed[i] = True
                        removeInvalidParenthesesHelper(i + 1, left_removed, right_removed - 1)
                        del removed[i]

        res, removed = [], {}
        (left_removed, right_removed) = findMinRemove(s)

        removeInvalidParenthesesHelper(0, left_removed, right_removed)

        return res

[3]:

sol = Solution1()

s = "()())()"
assert sol.removeInvalidParentheses(s) == ["()()()", "(())()"] or ["(())()", "()()()"]

s = "(a)())()"
assert sol.removeInvalidParentheses(s) == ["(a)()()", "(a())()"] or ["(a())()", "(a)()()"]

s = ")("
assert sol.removeInvalidParentheses(s) == [""]